#ifndef _RBT_H_
#define _RBT_H_


#include <stdio.h>
#include <stdlib.h>
#include <string.h>



// 父子节点
#define PARENT_NODE	1
#define CHILD_NODE	0

// 左右孩子
#define LEFT_NODE	1
#define RIGHT_NODE	0


// 节点颜色(创建新节点默认为红色，宏定义红色为0可以在memset后完成初始化为红色的操作)
#define RED			0
#define BLACK		1


// 树节点
typedef struct rbt_node
{
	/*! 数据 */
	int val;

	/*! 此节点的左右节点 */
	struct rbt_node* left;
	struct rbt_node* right;

	/*! 此节的父节 */
	struct rbt_node* parent;
	
	/*! 此节点是父节点的左节点还是右节点 */
	//int flag_left_or_right;

	/*!< 节点的高度 */
	int height;

	/*!< 节点的颜色 */
	int color;

} rbt_node_t;


// 树
typedef struct rbt
{
	/*! 树根 */
	struct rbt_node* root;

	/*! 树中的节点数 */
	int node_count;
} rbt_t;



int get_max_val(int a, int b);

// 一些辅助函数
int get_node_color(rbt_node_t* node);
int is_black(rbt_node_t* node);
int is_red(rbt_node_t* node);
rbt_node_t* set_node_color(rbt_node_t* node, int color);
rbt_node_t* set_black(rbt_node_t* node);
rbt_node_t* set_red(rbt_node_t* node);
rbt_node_t* get_sibling_ndoe(rbt_node_t* node);



rbt_t* creat_rbt();
int destroy_rbt();

int is_leaf_node(rbt_node_t* node);

rbt_node_t* creat_node(int key);
rbt_t* insert_node(rbt_t* tree, int key);

int after_add_node(rbt_t* tree, rbt_node_t* node);
int after_delete_node(rbt_t* tree, rbt_node_t* del, rbt_node_t* replace);

int delete_node(rbt_t* tree, int key);
int delete_leaf_node(rbt_t* tree, rbt_node_t* del, int flag);

rbt_node_t* search_node(rbt_node_t* root, int key);

rbt_node_t* get_rsb_min_node(rbt_node_t* root, rbt_node_t** parentNode);

int is_left_child(rbt_node_t* node);
int is_right_child(rbt_node_t* node);

int rotate_left(rbt_t* tree, rbt_node_t* grandpa);
int rotate_right(rbt_t* tree, rbt_node_t* grandpa);


void infix(rbt_node_t* root);
int level(rbt_node_t* root);




#endif // _RBT_H_
